1. Field of the Invention
The present invention relates generally to data communication networks and, in particular, to a method and apparatus for performing accelerated hierarchical address filtering and translation.
2. Description of Related Art
Address translation is the process of mapping an address, such as the network address contained in a packet, to some desired information. Examples of desired information include determining the output port of a switch to which a packet is to be sent and determining the address of the next-hop router for the routing of Internet Protocol (IP) datagrams. Address filtering is a process similar to address translation, except that rather than retrieving the data associated with an address, the process simply determines whether the address exists in a table of addresses. The term address translation, as used herein, includes both address translation and address filtering operations.
With respect to routing, addresses can be categorized as either flat addresses or hierarchical addresses. FIGS. 1A-1B illustrate examples of flat and hierarchical addresses. Flat addresses are addresses that have no internal structure that can be used in protocol processing of the address. Ethernet address 110 of FIG. 1A is an example of a flat address. Although Ethernet addresses have a structure (e.g., one part of the address denotes the manufacturer of the equipment using that address), that structure is not relevant to protocol processing operations, such as routing. Many techniques have been developed for accelerating flat address translation. As these techniques are well known to those skilled in the art, they are not further discussed herein.
Hierarchical addresses are addresses that have an internal structure that can be used in protocol processing of the address. Examples of hierarchical addresses include Internet Protocol (IP) v.4 addresses, IP v.6 addresses, E.164 addresses (used in ATM network protocol processing), and telephone numbers.
Telephone number 120 of FIG. 1B is used to illustrate the internal structure of a hierarchical address. Consider telephone number 120. The highest level of the hierarchy is denoted by area code 130, which is used to identify telephone numbers in area 135. The next level of hierarchy is central office code 140, which is used to identify telephone numbers in central office zone 145. The lowest level of the hierarchy is station number 150, which identifies the specific telephone subscriber 155 among those serviced by the station for central office zone 145.
The hierarchical structure of a telephone number is used when determining how to route a call through the telephone network. For example, if a call both originates and terminates in central office zone 145 (i.e., both the source and the destination numbers have central office code 140), then the telephone call passes only through the central office for central office zone 145. If a call both originates and terminates in area 135 (i.e., both the source and destination numbers have area code 130), no long-distance carrier is used to carry the call. Note that a flat address can be viewed as a hierarchical address with a single level of hierarchy. Thus, any address translation technique that operates on hierarchical addresses can also be applied to flat addresses.
Hierarchical addresses allow for processing of addresses without the need for storing information about all addresses to be processed. Information about entire classes of addresses is stored in a single entry. For example, if a call originates within area 135 and terminates in an area having a different area code, the correct action is to forward the call to a long distance carrier, regardless of the area code of the destination telephone number. Thus, a single entry in the table determines the handling of any telephone call to an area code other than area code 130.
In order to translate a specific telephone number into an action to be performed in the protocol processing of a call, a look-up table is used to store various hierarchical addresses, each corresponding to a specific action to be taken in routing the call.
FIG. 2A illustrates a typical prior art routing table used to route calls originating in area 135. In FIG. 2A, entry A represents a hierarchical address that matches all telephone numbers in the "908" area code and the "979" central office code. This is accomplished by inserting don't care (X) values into the entries to indicate any valid value in the corresponding digit of the address compared to the entry. In other words, table entry "908-979-XXXX" matches all telephone numbers between "908-979-0000" and "908-979-9999". Likewise, entry B represents all telephone numbers in the "908" area code and the "852" central office code. Entry C, in turn, represents all telephone numbers in the "908" area code regardless of their central office code. Finally, entry D represents all long distance telephone numbers. Any telephone number that is compared to the table entries matches one or more entries in the table (since all telephone numbers match entry D). For the table to operate correctly, however, it is necessary for the correct matching entry to be returned. The correct matching entry is the one at the lowest hierarchical level (i.e., the entry with the fewest X's).
For example, if the table is searched for the (908) 979-1035 telephone number, the matching entries are A, C and D. However, entry A is the correct matching entry having the lowest hierarchical rank and thus allowing for the most specific action (i.e., placing the call within the central office).
Current methods for translating hierarchical addresses are implemented in software and use tree structures, such as PATRICIA trees. PATRICIA trees are described on pages 481-493 of "The Art of Computer Programming, Vol. 3: Searching and Sorting" by Donald E. Knuth (Reading, Mass.: Addison Wesley, 1973), which is herein incorporated by reference in its entirety. FIG. 2B illustrates a switching table 200 which uses a PATRICIA tree to route calls originating in central office zone 145.
Telephone numbers are compared with table entries in order from top to bottom looking for a matching entry. The telephone number is first compared to entry A. If the area code of the telephone number is "908," subentries A.a, A.b and A.c are searched; otherwise the telephone number is compared to entry B, the long distance point-of-presence entry, which matches all telephone numbers.
This approach, however, is limited by the constraints of a software implementation: processing speed is typically slower than in equivalent hardware implementations and comparisons with table entries are typically performed in a sequential order.
Several techniques that utilize content addressable memories (CAMs) for searching a routing table are discussed in "Fast Routing Table Lookup Using CAMs" by Anthony J. McAuley and Paul Francis (1993 INFOCOM Proceedings) hereinafter "the McAuley article"!, which is herein incorporated by reference in its entirety. Prior art techniques, such as those described in the McAuley article, are summarized in FIGS. 3A-3C.
A content addressable memory (CAM) is a memory device that allows retrieval of information by specifying part of the stored information rather than by specifying a storage address. For example, if an entry "abcd" were stored in a CAM, the CAM could be instructed to return the complete contents of all locations containing "ab". CAMs are sometimes referred to as associative memories.
CAMs are generally classified as either binary or ternary CAMs. Binary CAMs store binary entries, while ternary CAMs store ternary entries. Binary entries are entries that contain only 0 or 1 values, while ternary entries are entries that contain 0, 1 or X (i.e., "don't care") values. Note that a single ternary entry can be expressed as two or more binary entries. In other words, a single ternary entry "1X0" can be represented by two binary entries "110" and "100", or a single ternary entry "1XX" can be represented by four binary entries "100", "101", "110" and "111", etc. As hierarchical addresses often comprise ternary values (e.g. "908-979-XXXX"), ternary CAMs require a smaller number of table entries to represent each hierarchical address than binary CAMs. However, ternary CAMs require more complex hardware and are generally more expensive than binary CAMs.
CAMs may be implemented using a variety of techniques and technologies. One common technique is to search all CAM entries simultaneously in parallel to find the desired entry. Other techniques include hardware implementations of techniques commonly associated with software, such as hashing, serial search, binary search, and various search techniques based on a tree data structure. As these techniques are well known to those skilled in the art, they are not further discussed herein.
The advantages of using CAMs for hierarchical address translation are higher performance and better price/performance ratio than using existing techniques.
A first prior art technique relies on the intrinsic priority encoding of entries stored in a CAM. Since the order in which entries are retrieved from a CAM can be predicted based on the location of the entries, address routing operations can be implemented by first storing the addresses in the table into the CAM in a given order and then searching the table for the address, as shown in FIG. 3A. In FIG. 3A, the addresses are first stored in the CAM in reverse hierarchical order in stage 310. The CAM is then searched for the address in stage 320. Since the entries are returned in reverse hierarchical order, the first matching entry returned by the search is the one with the lowest hierarchical rank, which is also the correct matching entry.
This technique, however, is not very useful in practice since it requires all the entries in the CAM to be sorted every time a new entry is added to preserve the inverse hierarchical ordering. To remedy this problem, the McAuley article proposes adding a priority field to table entries, as shown in FIG. 2C. FIG. 2C illustrates the table of FIG. 2A augmented by a priority field added to each entry. The priority field is used to represent the hierarchical order of the entries and allows the CAM to be searched in hierarchical order without requiring all entries to be re-sorted when a new entry is added to the CAM. For example, in FIG. 2C, entry D, which matches all telephone numbers, has the highest hierarchical level 1.
While hierarchical addresses can be directly stored in ternary CAMs, in order to be stored in binary CAMs they must first be translated into binary format. As discussed above, a ternary address can be translated into two or more binary addresses. However, the number of binary addresses needed to represent a ternary address is 2.sup.m where m is the number of don't care digits in the ternary address. For example, ternary address "908-979-XXXX" would be translated into 10,000 binary addresses, "908-979-0000" through "908-979-9999". As the cost of CAMs is dependent on the number of entries they can store, the number of binary addresses needed to represent large hierarchical addresses renders this solution undesirable.
To solve this problem, the McAuley article proposes translating a ternary hierarchical address into a binary address and a binary priority mask, as shown in FIG. 4A. The binary address has a 1 in the positions in which the ternary address has a 1, and 0s in the other positions. The mask contains a 0 in the positions in which the ternary address has an X, and 1s in the other positions. As a result, each bit in the binary address, together with a corresponding bit in the priority mask, accurately indicates the value of a corresponding bit in the ternary entry, as shown in FIG. 4A. The binary addresses are stored in the CAM, while the binary masks indicate which bits of the stored addresses are compared to the search address during searches of the CAM. As only one binary address is generated for each ternary address, the size of the CAM is greatly reduced.
In order for values to be correctly stored in the binary CAM, ternary addresses must be translated into unique binary addresses. FIG. 4B, for example, shows two ternary entries that generate the same binary address, albeit with different masks. If more than one ternary value is translated into a single binary address stored in the CAM, only one set of data can be stored in the CAM (in the location of the binary address) and thus only one ternary address can be correctly translated. This problem is remedied by treating certain ternary values as invalid to ensure that all ternary values are translated into unique binary addresses. For example, in IP v.4, 0 is not a legal value for the lowest level of the hierarchical address.
A second prior art technique consists of searching a binary CAM for portions of an address specified by a priority mask, as shown in FIG. 3B. In FIG. 3B, a binary CAM is first searched for a binary address using a binary priority field at the lowest hierarchical level (i.e., the most specific hierarchical level) in stage 340. Stage 345 then determines whether the search found any matching entries, in which case the first of the matching entries is retrieved in stage 355; otherwise the CAM is searched again for the same address and a priority field at the next higher hierarchical level. The first matching entry is the correct matching entry, as it has the lowest hierarchical level of any matching entry.
This technique, however, requires in the worst case a search for each hierarchical level of the entries in the CAM.
A third prior art technique, therefore, uses a ternary CAM in place of a binary CAM to reduce the number of searches of the CAM needed in the worst case to find a matching entry. A ternary CAM is a binary CAM that can handle "don't care" values (represented by the symbol X) which match both 1 and 0 values. This technique is illustrated in FIG. 3C. Unlike with binary CAMs, ternary addresses are stored in the ternary CAM together with the corresponding binary priority fields representing the hierarchical level of the addresses. The ternary CAM is then searched with an address to be translated and a priority field in which all bits, except for the most significant bit, have a don't care value. After each search, a don't care bit of the priority field is replaced by a 1 or a 0 (as explained below), until a binary priority field is obtained. An entry matching the address and the binary priority field is the correct matching entry.
In FIG. 3C, the ternary CAM is first searched for an address and a priority field having a 1 in the most significant bit position and an X in all other bit positions, in stage 360. Stage 365 then determines if there are any matching entries, in which case the operation proceeds to stage 375; otherwise the least significant bit in the priority field having a value of 1 is replaced by a value of 0. Stage 375 then determines whether any bits of the priority field have a value of X, in which case the most significant bit in the priority field having a value of X is replaced by a value of 1 in stage 380. The CAM is then searched for the address and the modified priority field, in stage 385. Stage 390 determines whether there is a single matching entry, in which case the matching entry is retrieved from the CAM in stage 395; otherwise stages 365-390 are repeated until the test of stage 390 is satisfied and the operation terminates. Thus, one X is resolved (i.e. replaced by a 1 or a 0) after each search until a matching entry is found.
This technique requires in the worst case a number of searches equal to the number of bits used to represent the priority field (i.e., if N is the number of hierarchical levels represented by the priority field, log.sub.2 N searches are required to find a matching entry at the lowest hierarchical level, as all bits of the priority mask must be resolved).
There is thus a need for an improved method and apparatus for performing fast hierarchical address translation.